/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-11-15
 * Time: 22:12
 */

import java.util.*;

// 416. 分割等和子集

class Solution3 {
    //使用 HashSet+动态规划的方式来求解问题，set的去重和哈希表的查找的O(1)
    public boolean canPartition(int[] nums) {
        //分割等和子集
        //和之前做的0-1背包问题很像，我觉得我们需要做的也就是在这个nums数组中，找到能凑成所有元素和的 一半的组合就行了（每个元素只使用一次）
        //我觉得如果nums这个数组中的所有元素的和的 一半是一个小数，我觉得那应该就无法分割，直接返回false即可
        int len=nums.length;
        int sum=0;
        for(int i=0;i<len;i++){
            sum+=nums[i];
        }
        int rder=sum%2;//余数，如果余数为0，就代表整除了，如果余数为1，就代表无法整除2，就直接返回false
        if(rder==1){
            return false;
        }

        int midSum=sum/2;//数组所有元素的和的  一半

        //在数组nums中找，是否能够凑出和为midSum的组合

        //相当于必须把背包装满的0-1背包问题

        //借助HashSet来实现一种滚动的动态规划的思想（以示例1为例）nums = [1,5,11,5]
        //那么放到set中的元素值的变化如下：
        //1
        //1        5        6
        //1 5 6       11        12 16 17
        //1 5 6 11 12 16 17           5         6 10 11 16 17 31 22


        //set具有去重的功能，这里为了方便表示和观察在举例子的时候没有去重，但是在代码中set会去重的
//当每次放到set中的新的nums数组中的值nums[i]的时候，就让现有的set中的值set.get(j)都加上这个新值nums[i],   如果set.get(j)+nums[i]这个值等于我们要找的midSum,就可以直接返回true了，   要不然就得把这个值继续放到set中，继续进行迭代了。
//当然对于每次遍历到的nums[i]的值也会被放到set中
        HashSet<Integer> set=new HashSet<>();
        set.add(nums[0]);//先把数组中的第一个元素放到set中
        if(nums[0]==midSum){
            //先判断一下 数组中的第一个元素是否符合条件，符合就返回true，不符合就继续寻找
            return true;
        }

        //开始寻找 是否有合适的元素集合满足和的条件
        for(int i=1;i<len;i++){

            //遍历set中的值
            int size=set.size();
            int[] array=new int[size+1];//使用array数组来接收遍历set所产生的中间值们
            int j=0;//标记array数组的下标值
            for(Integer s : set){
                int ret=s+nums[i];

                //判断每次加和后的值是否满足返回条件
                if(ret==midSum){
                    //满足，返回true
                    return true;
                }else{
                    //不满足，把新得到的值放到array数组中，回头再把array数组中的值依次放到set中
                    array[j++]=ret;
                }
            }

            //当然对于每次遍历到的nums[i]的值也会被放到set中
            array[size]=nums[i];

            // 把array数组中的值依次放到set中
            for(j=0;j<=size;j++){
                set.add(array[j]);
            }
        }

        return false;

    }

}